package god_zuo.day01;

/**
 * @Author 孔德成
 * @Slogan 致敬大师，致敬未来的你
 * @dsc 异或运算：不同为0，相同为1（无进位相加）
 */
public class XOR {
    public static void main(String[] args) {
        // 性质1：0^N=N N^N=0
        System.out.println("0^2=" + (0 ^ 2));
        System.out.println("2^2=" + (2 ^ 2));
        System.out.println("-----------------");
        // 性质2：满足交换律和结合律
        // a^b=b^a a^b^c=a^(b^c)
        XOR.swap(1, 2);
        XOR.test1();
        XOR.test2();
    }

    // 使用异或运算完成变量交换
    // 这样做的前提是，运算数必须处于不同内存区域
    // 数组中交换 i 与 j，注意 i!=j才可以这样用
    public static void swap(int a, int b) {
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
        System.out.println("a=" + a + " b=" + b);
    }

    /**
     * 只有一个数出现了奇数次，其他所有数全部出现偶数次
     * 找出出现奇数次的数字
     */
    public static void test1() {
        int[] array = {1, 1, 1, 2, 2, 3, 4, 4, 3};
        int eor = 0;
        for (int i : array) {
            eor ^= i;
        }
        System.out.println(eor);
    }

    /**
     * 只有两种数出现了奇数次，其他所有数全部出现偶数次
     * 找出这两种数
     */
    public static void test2() {
        int[] array = {1, 2, 3, 1, 4, 5,5,4};
        int eor = 0;
        for (int i : array) {
            eor ^= i;
        }
        // eor = a^b
        // 因为 a!=b, 所以 eor!= 0,所以 eor 必定有一位是1
        // 提取出最右的1
        int rightOne = eor & (~eor + 1);
        int onlyOne = 0;
        for (int i : array) {
            if ((i & rightOne) == 1) {
                onlyOne ^= i;
            }
        }
        System.out.println("a=" + onlyOne + " b=" + (eor ^ onlyOne));
    }
}
